package tree;

import java.util.Stack;

public class Traverse {

	public static void inOrderItr(Node root) {
		Stack<Node> stack = new Stack<Node>();
		Node p = root;
		do {
			while (p != null) {
				stack.push(p);
				p = p.left;
			}
			p = stack.pop();
			System.out.println(p.value);
			p = p.right;
		} while (p != null || !stack.empty());
	}

	public static void inOrderItr1(Node root) {
    Stack<Node> stack = new Stack<Node>();
    Node p = root;
    while (p != null || !stack.empty()) {
      if (p != null) {
        stack.push(p);
        p = p.left;
      } else{
        p = stack.pop();
        System.out.println(p.value);
        p = p.right;
      }
    }
  }

	public static void inOrderRec(Node root) {
		if (root != null) {
			inOrderRec(root.left);
			System.out.println(root.value);
			inOrderRec(root.right);
		}
	}

	public static void preOrderItr(Node root) {
		Stack<Node> stack = new Stack<Node>();
		Node p = root;
		stack.add(p);
		while(!stack.isEmpty()){
			p = stack.pop();
			System.out.println(p.value);
			if(p.right != null){
				stack.add(p.right);
			}
			if(p.left != null){
				stack.add(p.left);
			}			
		}
	}
	
	public static void preOrderRec(Node root) {
		if (root != null) {
			System.out.println(root.value);
			preOrderRec(root.left);
			preOrderRec(root.right);
		}
	}
	
	public static void backOrderItr(Node root) {
		if(root == null)
			return;
		Stack<Node> stack = new Stack<Node>();
		stack.push(root);
		Node prev = null;
		while(!stack.isEmpty()){
			Node n = stack.peek();
			if(prev == null || prev.left == n || prev.right == n){
				if(n.left != null)
					stack.push(n.left);
				else if(n.right != null)
					stack.push(n.right);
				else
					System.out.println(stack.pop().value);
			}
			else if(n.left == prev){
				if(n.right != null)
					stack.push(n.right);
				else
					System.out.println(stack.pop().value);
			}else{
				System.out.println(stack.pop().value);
			}
			prev = n;
		}
	}
	
	public static void backOrderItr1(Node root){
		if(root == null)
			return;
		Stack<Node> stack = new Stack<Node>();
		Stack<Integer> tag = new Stack<Integer>();
		Node p = root;
		do{
			while(p != null){
				stack.push(p);
				tag.push(0);
				p = p.left;
			}
			if(!stack.isEmpty()){
				if(tag.peek() == 1){
					System.out.println(stack.pop().value);
					tag.pop();
				}else{
					p = stack.peek();
					if(!stack.isEmpty()){
						p = p.right;
						tag.pop();
						tag.push(1);
					}
				}
			}
		}while(p!= null || !stack.isEmpty());
		
	}

	public static void backOrderRec(Node root) {
		if (root != null) {
			backOrderRec(root.left);
			backOrderRec(root.right);
			System.out.println(root.value);
		}
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Traverse.inOrderItr1(Node.create());
	}

}
